package 力扣._2537_统计好子数组的数目;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

class Solution {
    public long countGood(int[] nums, int k) {
        // 滑动窗口， 窗口内数对的个数由hash表维护
        long ans = 0;
        Map<Integer,Integer> map = new HashMap<>();
        int l=0,r=0,n = nums.length, count=0;   // count当前窗口内相同数对的个数
        // 枚举右端点
        while(r<n){
            int t = nums[r];
            if(map.containsKey(t)){
                map.put(t, map.get(t)+1);
            }else{
                map.put(t,1);
            }
            if(map.get(t)>1){
                count += map.get(t)-1;
            }

            while(count>=k){
                ans += n - r;
                // 将左边界移除
                int lt = nums[l];
                map.put(lt, map.get(lt)-1);
                if(map.containsKey(lt))
                    count -= map.get(lt);
                l++;
            }
            r++;
        }
        return ans;
        
    }
}